package com.lwl.Algorithmic_data_structure.class04归并;

/**
 * 给一个数组arr，以及两个整数lower，upper；找出arr中 子数组 累加和 在【lower，upper】范围上的个数
 */
public class Code04CountOfRangeSum {

    public static int countOfRangeSum(int[] arr, int lower, int upper) {
        // 1. 转化为前缀和数组sums
        // 2. 进行归并排序,在merge中进行额外操作(右组处于i位置,求有多少左组的数位于 [sums[i] - upper,sums[i] - lower )
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int[] sums = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            sums[i] += arr[i];
        }
        return mergeSort(sums, 0, sums.length - 1, lower, upper);
    }

    private static int mergeSort(int[] sums, int left, int right, int lower, int upper) {
        if (left == right) {
            if (sums[left] >= lower && sums[left] <= upper) {
                return 1;
            } else {
                return 0;
            }
        }
        int mid = left + ((right - left) >> 1);
        return mergeSort(sums, left, mid, lower, upper)
                + mergeSort(sums, mid + 1, right, lower, upper)
                + merge(sums, left, mid, right, lower, upper);
    }

    private static int merge(int[] sums, int left, int mid, int right, int lower, int upper) {
        int ans = 0;
        // 使用一个窗口来模拟当前符合的范围,看能圈住左组中的多少个数
        // 因为右组是有序的,所以这个窗口的范围大小也是有序(递增/递减)的,不会回退,所以遍历的时间复杂度仍然是oN
        int windowsL = left;
        int windowsR = left;

        for (int i = mid + 1; i <= right; i++) {
            int min = sums[i] - upper;
            int max = sums[i] - lower;
            while (windowsL <= mid && sums[windowsL] < min) {
                windowsL++;
            }
            while (windowsL <= mid && sums[windowsR] <= max) {
                windowsR++;
            }
            //现在的窗口是 [min,max),[14,15)代表范围内有14一个数,[14,14)代表范围一个数都没有
            ans += windowsR - windowsL;
        }
        int[] help = new int[right - left + 1];
        int p1 = left;
        int p2 = mid + 1;
        int index = 0;
        while (p1 <= mid && p2 <= right) {
            help[index++] = sums[p1] < sums[p2] ? sums[p1++] : sums[p2++];
        }
        while (p1 <= mid) {
            help[index++] = sums[p1++];
        }
        while (p2 <= right) {
            help[index++] = sums[p2++];
        }
        for (int i = 0; i < index; i++) {
            sums[left + i] = help[index];
        }
        return ans;
    }

}
